10365. Цепочки ромашек

Каждый день, прогуливаясь по ферме, корова Бесси навещает своё любимое пастбище, где растут n цветков (все разноцветные ромашки), пронумерованные от 1 до n и выстроенные в ряд. Цветок i имеет p_i лепестков.

Будучи начинающим фотографом, Бесси решила сделать несколько снимков этих цветков. В частности, для каждой пары индексов (i, j), где 1 ≤ i ≤ j ≤ n, она фотографирует все цветки с номерами от i до j (включая концы отрезка).

Позже, рассматривая полученные фотографии, Бесси замечает, что на некоторых из них присутствует средний цветок – цветок с p лепестками, где p равно среднему количеству лепестков среди всех цветков на данной фотографии.

Определите, на скольких фотографиях Бесси встречается средний цветок.

Вход. Первая строка содержит число n (1 ≤ n ≤ 100).

Вторая строка содержит n целых чисел p₁, ..., p_n (1 ≤ p_i ≤ 1000).

Выход. Выведите количество фотографий, на которых присутствует средний цветок.

Пример входа	Пример выхода
4 1 1 2 3	6

РЕШЕНИЕ

перебор

Анализ алгоритма

Решение за O(n³). Переберем все возможные интервалы [i; j] (0 ≤ i ≤ j < n) и проверим, содержится ли в них средний цветок. Для этого должно существовать такое p_k (i ≤ k ≤ j), что

p_k = totalPetals / (j – i + 1),

где totalPetals – общее число лепестков у цветков на интервале [i; j].

Реализация алгоритма – O(n³)

Объявим массив для хранения количества лепестков p_i в каждом цветке.

#define MAX 101

int p[MAX];

Читаем входные данные.

scanf("%d", &n);

for (i = 0; i < n; i++)

scanf("%d", &p[i]);

Количество фотографий, на которых присутствует средний цветок, будем хранить в переменной photos.

photos = 0;

Переберём все возможные интервалы [i; j] (0 ≤ i ≤ j < n) и проверим, совпадает ли среднее арифметическое числа лепестков цветков на этом интервале с количеством лепестков хотя бы одного из них.

for (i = 0; i < n; i++)

for (j = i; j < n; j++)

{

В переменной totalPetals храним общее количество лепестков у цветков на интервале [i; j].

int totalPetals = 0;

for (k = i; k <= j; k++)

totalPetals += p[k];

Перебираем значения p_k на интервале [i; j] (i ≤ k ≤ j). Если p_k совпадает со средним арифметическим числа лепестков среди всех цветков фотографии на интервале [i; j], то увеличиваем значение photos на 1. Для этого должно выполняться условие:

p_k = totalPetals / (j – i + 1)

present = 0;

for (int k = i; k <= j; k++)

if (p[k] * (j - i + 1) == totalPetals) present = 1;

if (present) photos++;

}

Выводим ответ.

printf("%d\n", photos);